package com.intelli.eve.core.data_structure.priority_queue;

import java.util.Comparator;
import java.util.NoSuchElementException;

/**
 * Author: Sergey42
 * Date: 21.12.2014 15:50
 */
public class MinPQ<T> extends AbstractPQ<T> {

    public MinPQ(int initCapacity) {
        super(initCapacity);
    }

    public MinPQ(int initCapacity, Comparator<T> comparator) {
        super(initCapacity, comparator);
    }

    public MinPQ(T[] keys) {
        super(keys);
    }

    @Override
    protected MinPQ newPQ(int size) {
        return new MinPQ(size);
    }

    @Override
    public T pollTop() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        exchange(1, size);
        T min = pq[size--];
        sink(1);
        pq[size + 1] = null;         // avoid loitering and help with garbage collection
        if ((size > 0) && (size == (pq.length - 1) / 4)) resize(pq.length / 2);
        assert isNormalizedHeap();
        return min;
    }

    @Override
    protected boolean isMore(int i, int j) {
        return greater(i, j);
    }
}
